This disclosure is generally related to an apparatus and method for improving the scheduling of user traffic in a network mapped to “Best Effort” (BE) Quality of Service (QoS) categories. In particular, this disclosure is related to an apparatus and method for providing a minimum reserved traffic rate (MRTR) for BE communications in a congested network environment. More particularly, this disclosure is related to Code Division Multiple Access (CDMA) and Worldwide Interoperability for Microwave Access (“WiMAX”) technologies under the IEEE 802.16e standard and WiMAX Forum System Profile 1.X, for example, in which a base station (BS) schedules uplink and downlink traffic to multiple mobile stations (MS).
FIG. 1 depicts the architecture of an exemplary WiMAX network implemented in accordance with various aspects of IEEE Standard 802.16e. In FIG. 1, BS 110 may communicate with one or more Mobile Stations/Subscriber Stations (MS/SS) 130a-130n over network 120 via an associated communication channel 140a-140n. The terms “SS” and “MS” may be used interchangeably, although it is recognized that MS implies the use of mobility enhancements. MS/SS 130a-130n may be relatively fixed or immobile terminal equipment, or may be equipment that includes the mobility functions of a MS, e.g., a cell phone or laptop computer traveling in an automobile or airplane. Various factors such as the existence of ambient interference around the SS or BS, movement of the SS, and other factors may degrade or otherwise alter the channel condition of the communication channel, making the use of HARQ desirable to ensure reliable communications over channels 140a-140n. HARQ uplink Acknowledgement Channels (ACKCH) 150a-150n allow each MS/SS 130a-130n to acknowledge packet receipt to the BS by use of a HARQ signal transmission over a dedicated HARQ ACK channel. Channel Quality Indicator (CQI) channels 160a-160n provide a path for the MS or SS to identify the relative quality of the communication channel to BS 110 using known techniques.
WiMAX systems present various traffic scheduling challenges. For example, the quality of the wireless channel is typically different for different users and randomly changes with time (on both slow and fast time scales). Further, wireless bandwidth is considered to be a scarce resource that needs to be used efficiently (i.e., you can not overprovision the wireless link). In addition, an excessive amount of interference and higher error rates are typically experienced. Scheduling decides the modulation coding scheme (MCS) and affects error rate, and error rate affects the choice of MCS. In general, mobility complicates resource allocation.
Generally, system scheduling considerations include total available bandwidth; service flow specific scheduling policy; service flow QoS parameters; data queue backlog; Request/Grant Mechanisms (e.g., contention, polling, piggyback); connection air link quality; impact of burst allocation on PHY layer (i.e., burst concurrency, interference property, and memory/processing limitations); and the use of Acknowledgement Repeat Request (ARQ) and/or Hybrid ARQ (H-ARQ).
In a variable wireless link, throughput, latency/delay, and transmission errors vary much more widely over a wireless connection because of constantly changing radio signal conditions and extensive digital radio processing. Standard internet protocols, designed for use over a more stable wire-based connection, are not well-suited to handle these variations. For shared wireless resources, the same wideband radio channel must be shared among many user sessions and each user session may involve many different types of data streams and protocols. Some applications require bursty, time-sensitive, small-packet data transmissions, while other applications require long, error-sensitive large-packet data streams. To provide acceptable QoS, the network must be able to identify and combine many different types of traffic from many different users without compromising the performance of any of the different user applications.
To support multimedia applications, the WiMAX IEEE 802.16e standard defines five types of data delivery service flows for downlink (DL) flows and five corresponding scheduling services for uplink (UL) flows: UGS—Unsolicited Grant Service, with constant bit-rate services (CBR); rtPS—Real Time Polling Service, with variable bit-rate, but sensitive to delay; ertPS—Extended Real Time Polling Service, for VoIP with silence suppression, similar to CBR with gaps; nrtPS—Non-real Time Polling Service, time insensitive, but require a minimum bandwidth allocation; and BE—Best Effort. Uplink is differentiated from downlink because uplink flows (except UGS) involve some form of request/grant mechanism for resource allocations. Table I summarizes the various WiMAX data service types.
TABLE IWiMAX Data Delivery ServicesDL data delivery serviceUL scheduling serviceTargeted trafficUnsolicited grant serviceUnsolicited grantConstant bit rate(UGS)service (UGS)(CBR) services, TDMservicesExtended real-time Vari-Extended real-timeVoIP with silenceable Rate (ERT-VR)polled service (ertPS)suppression/activitydetectionReal-time Variable RateReal-time polledStreaming audio &(RT-VR)service (rtPS)videoNon-real-time VariableNon-real-time polledFile transfersRate (NRT-VR)service (nrtPS)Best Effort (BE)Best Effort (BE)Web browsing, e-mail,etc.
Each of these service flow types has a different QoS requirements and is designed to support different types of traffic streams. The order of priority given to services while transmitting is generally as follows: UGS>ertPS>rtPS>nrtPS. However, the particular scheduling mechanism is generally left to be defined by proprietary implementations.
Since the BS governs resource scheduling, uplink resources must either be allocated automatically on a periodic basis, or requested individually as needed by the MS. Resources for UGS and ertPS service flows are periodically allocated according to an unsolicited grant interval (UGI) defined for each service flow. The ertPS service flows can also dynamically request additional resources, i.e., more throughput, as described below. Resources for rtPS, nrtPS and BE service flows must be individually requested (usually triggered by data in the MS buffer.) The BS can automatically offer dedicated uplink opportunities for specific ertPS, rtPS and nrtPS service flows to request bandwidth on a periodic basis (unsolicited polling interval). The ertPS, rtPS, nrtPS and BE service flows can also request bandwidth during a shared uplink opportunity, subject to contention. Once UL resources have been granted, requests for additional UL resources can be “piggybacked” on existing allocations.
While WiMAX defines the QoS parameters for each service flow type, it does not specify how the scheduler uses these parameters to allocate air interface resources. Radio Access Network (RAN) suppliers have employed different scheduling algorithms. Not all suppliers directly consider all the QoS parameters when allocating air interface resources. In some cases, suppliers assume a particular scheduling algorithm will minimize latency or jitter, without actually measuring and adjusting allocations to achieve the targeted performance.
A variety of conventional standalone mechanisms are used to provide different levels of control over user performance. Call Admission Control (CAC) used for non-BE flows (e.g., “real-time” voice or data) can be used to set some resources aside for BE. Traffic priority parameters can be used for intra-user distinction. Thresholds for minimum reserved traffic rate (MRTR) and maximum sustainable traffic rate (MSTR) are also used to control throughput. However, these conventional approaches have drawbacks.
FIGS. 2A and 2B illustrate conventional concepts of assigning different throughput parameters (related to available bandwidth) for each of three BE user classes, i.e., Gold, Silver, and Bronze users. These throughput parameters include a maximum sustainable traffic rate (MSTR) for each of the three user classes, i.e., MSTR_G, MSTR_S, and MSTR_B (FIG. 2A), and minimum reserved traffic rate (MRTR) for each of the three user classes, i.e., MRTR_G, MRTR_S, and MRTR_B (FIG. 2B). Gold class service typically may involve the highest user fee and have the highest targeted bandwidth. Silver class service involves a medium level of user fee, and less bandwidth than Gold class service. Bronze class service may involve the lowest fee with generally good bandwidth, but less bandwidth than both Gold and Silver class service.
There are various WiMAX scheduling concepts. Conventionally, BE is the lowest priority class, with no minimum rate guarantees, hence the term “best effort”. However, most service provider revenues typically come from traffic served by BE. Current network traffic schedulers allow BE user performance to progressively degrade as system load increases. While inter-user prioritization is possible allowing an arbitrarily defined “Gold” class to get better performance relative to “Silver” and “Bronze” classes, conventional gold user performance continues to degrade with the rest of the user classes as system load increases, without any option for the service provider to set a floor to performance degradation. Performance degradation can occur due to network congestion (outside of BS control), or due to additional load from newly admitted BE users (no call admission control is used for BE).
Inter-Class Scheduling allocates resources among different types of service flows based on strict priority. Resources for control and management traffic are allocated before user traffic, and resources for real-time service flows (UGS, ertPS) are allocated before resources for non-real-time (nrtPS) and best effort (BE) service flows. In contrast, Intra-Class Scheduling allocates resources among service flows of the same type differently depending upon the type of flow. Resources for control messages are typically allocated before management messages, resources for real-time service flows are typically allocated relative to the QoS parameters assigned to the service flow and adjusted accordingly to attempt to achieve the desired QoS for all service flows, and resources for nrtPS and BE service flows are typically allocated based on the user's signal conditions and the relative priority assigned to the users' traffic. Generally, all throughput rates are limited to a maximum throughput rate, but may burst above this rate (to a maximum burst rate) if resources are available. In addition, HARQ/ARQ can also be enabled/restricted/disabled per service flow to reduce latency and jitter.
The WiMAX Access Service Network (ASN) employs admission control and sophisticated resource scheduling to manage, but not guarantee, the QoS. The ASN is a set of network functions that include network discovery and selection of the preferred Connectivity Service Network/Network Service Provider (CSN/NSP), network entry with IEEE 802.16e-2005 based layer 2 connectivity and Authentication, Authorization, and Accounting (AAA) proxy, Relay function for IP Connectivity, radio resource management, multicast and broadcast control, intra-ASN mobility, foreign agent functionality for inter-ASN mobility, paging and location management, accounting assistance, data forwarding, service flow authorization, QoS, and Admission Control & Policing. The WiMAX ASN also marks traffic to enable other networks/elements to provide QoS consistent with the air interface.
WiMAX uses scheduling to determine QoS. All traffic is classified into separate service flows, as mentioned above. Each service flow is assigned different QoS parameters that govern minimum and maximum throughput rates, maximum latency and jitter, etc. A resource scheduler in the BS allocates air interface resources differently for each service flow type. As mentioned above, traffic within the same service flow type may be further differentiated by traffic priority values assigned to users. The resource scheduler also dynamically accounts for users' signal conditions when allocating non-real-time resources. In general, allocations to users in better signal conditions are weighted so they receive more resources (to maximize overall sector throughput), but an operator can adjust fairness to ensure users in poor signal conditions receive reasonable throughput. The WiMAX Radio Access Network (RAN) marks traffic according to the service flow type to enable consistent end-to-end QoS across multiple networks.
WiMAX also uses Admission Control for QoS. Admission control considers the QoS requirements for real-time service flows to determine whether they can be met with available air interface resources before activating the service flow. Available air interface resources can either be statically defined or dynamically calculated based on recent PHY (layer 1 of the OSI 7-layer model) performance. Admission control is performed by the BS during network entry and re-entry for statically-provisioned service flows (e.g. initial service flows). Admission control is also performed by the BS in response to dynamic BS-initiated or MS-initiated requests to create service flows. Further, Admission control is performed by the BS during handovers. Admission control can be used to limit the amount of total air interface resources that are consumed by real-time service flows. Since real-time service flows are allocated resources before non-real-time and best effort service flows, this feature prevents real-time traffic from “starving” best effort traffic.
So-called traffic “starvation” is similar in effect to program deadlock. Two or more programs become deadlocked together when each of them is waiting for a resource occupied by another program in the same set. Similarly, one or more network service flows are in starvation when each of them is waiting for system resources that are used by service flows that may or may not be in the same set that are starving. Such “starvation” is obviously an undesirable situation in a communications network. Most current vendors use CAC to limit starvation for BE users.
FIG. 3 illustrates a conventional allocation between BE and non-BE traffic in an uncongested BE traffic condition. For example, reference symbol “A” represents the current throughput (bandwidth allocation) of BE traffic, e.g., Gold BE service flow 1 (SF1) is maintained at least at the MRTR_G level; Silver BE service flow 2 (SF2) is maintained at least at the MRTR_S level; and Bronze BE service flow 2 (SF2) is maintained at least at the MRTR_B level. Reference symbol “B” represents the current loading of non-BE traffic (e.g., “real-time” traffic). Reference symbol “X” represents an operator-configurable bandwidth (BW) allocation reserved for the various user classes of BE service. The term “(100-X)” represents a percentage of BW reserved for non-BE service flows to which CAC is applied.
FIG. 4 illustrates an allocation between BE and non-BE traffic in a congested BE traffic condition in which additional BE users (represented by reference symbol “C”) are allowed to join the network, resulting in a reduction in BW per Gold user (represented by reference symbol “D”) and degraded performance for Gold users 1 and 2.
FIG. 5 illustrates conventional problems with the allocation of BW to different user classes. For example, in Case 1, an undesirable situation is encountered in which a Gold user's throughput falls below the MSTR_G level, while Silver and Bronze BE users throughput remains at their respective MSTR_S and MSTR_B levels. Case 2 illustrates another undesirable situation in which excessive Gold user BW is allocated to provide throughput above the MSTR_G level, resulting in Silver and Bronze users falling below their respective MSTR_S and MSTR_B levels. Service providers and their customers would prefer to avoid both of these undesirable situations.
What is needed is a network traffic scheduler implementation in which principles of inter-user traffic priority are combined with BE QoS categories, CAC, and anti-starvation to allow desired BE user behavior. What is further needed is a scheduling apparatus and method that allows a service provider to selectively configure the scheduler to vary between a simple weighted round-robin scheduling process and a modified process that sets lower bounds on throughput for higher priority BE users, and which allows the service provider to make tradeoffs between different service classes or users in the same BE category such that BE user performance degradation with increasing system load is prevented or reduced.